package com.zl.learning.arithmetic.sort;

import java.util.Arrays;

import static com.zl.learning.arithmetic.util.SortUtil.printArray;

/**
 * 直接选择排序
 * 将整个数组视为无序队列,每一次对无序队列的循环都将最小元素放到队头并入有序队列
 * <p>
 * 选择排序提高了冒泡排序的性能，它每遍历一次列表只交换一次数据，即进行一次遍历时
 * 找 到最大的项，完成遍历后，再把它换到正确的位置。和冒泡排序一样，第一次遍历后，
 * 最大的数 据项就已归位，第二次遍历使次大项归位。这个过程持续进行，一共需要 n-1
 * 次遍历来排好 n 个数 据，因为最后一个数据必须在第 n-1 次遍历之后才能归位。
 */
public class SelectSort {

    /**
     * 选择排序
     */
    private static void selectSort(int[] a) {
        int time = 1;
        //选择排序的优化
        for (int i = 0; i < a.length - 1; i++) {// 做第i趟排序
            int k = i;
            for (int j = k + 1; j < a.length; j++) {// 选最小的记录
                if (a[j] < a[k]) {
                    k = j;//记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if (i != k) {
                int temp = a[i];
                a[i] = a[k];
                a[k] = temp;
            }
            System.out.println("第" + (time++) + "次外循环,数组此时为:" + Arrays.toString(a));
        }
    }

    public static void main(String[] args) {
        int[] a = {3, 7, 5, 2, 10, 9, 4, 6};
        printArray(a);
        selectSort(a);
        printArray(a);
    }
}
